﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.DynamicProgramming
{
    //完全背包问题
    //如果求组合数就是外层for循环遍历物品，内层for遍历背包。
    //如果求排列数就是外层for遍历背包，内层for循环遍历物品。
    class BackpackComplete
    {
        //有N件物品和一个最多能背重量为W的背包。
        //第i件物品的重量是weight[i],得到的价值是value[i]
        //每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大
        //完全背包和01背包唯一不同的地方就是，每种物品有无限件
        public void BackpackCompleteProblem()
        {
            int[] weight = { 1, 3, 4 };//物品重量
            int[] value =  { 15, 20, 30 };//物品价值
            int bagWeight = 4;//背包重量

            //重量为i的背包装入的物品最大价值为dp[i]
            int[] dp = new int[bagWeight + 1];
            dp[0] = 0;

            //对于完全背包来说，两个for的嵌套顺序无所谓
            //因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。
            for (int i = 0;i<weight.Length;i++)
            {// 遍历物品
                for (int j = weight[i];j<=bagWeight;j++)//从小到大遍历，与01背包不同的地方，因为可以添加多次
                {// 遍历背包容量
                    dp[j] = Math.Max(dp[j], dp[j - weight[i]] + value[i]);
                }
            }
            Console.WriteLine(dp[bagWeight]);
        }

        //=======================================力扣518 零钱兑换2
        //给定不同面额的硬币和一个总金额。
        //写出函数来计算可以凑成总金额的硬币组合数。
        //假设每一种面额的硬币有无限个
        //0 <= amount (总金额) <= 5000
        //1 <= coin (硬币面额) <= 5000
        //硬币种类不超过 500 种
        public int Change(int amount, int[] coins)
        {
            //凑成总金额j的货币组合数为dp[j]
            int[] dp = new int[amount + 1];

            dp[0] = 1;

            for(int i = 0;i<coins.Length;i++)
            {
                for(int j = coins[i];j <= amount;j++)
                {
                    //求装满背包有几种方法，一般公式都是：dp[j] += dp[j - nums[i]];
                    dp[j] += dp[j - coins[i]];
                }
            }
            return dp[amount];
        }

        //===========================================力扣377 组合总数4
        //给你一个由不同整数组成的数组，和一个目标整数target。
        //请你从nums中找出并返回总和为target的元素组合的个数
        //1 <= nums.length <= 200
        //1 <= nums[i] <= 1000
        //nums 中的所有元素 互不相同
        //1 <= target <= 1000
        //顺序不同的序列被视作不同的组合。
        public int CombinationSum4(int[] nums, int target)
        {//(其实是求排列）

            int[] dp = new int[target + 1];
            dp[0] = 1;
            for (int i = 0; i <= target; i++)
            {// 遍历背包(求排列）
                for (int j = 0; j < nums.Length; j++)
                {// 遍历物品
                    if (i>=nums[j])
                        dp[i] += dp[i - nums[j]];
                }
            }
            return dp[target];
        }

        //=========================================力扣70 爬楼梯(改）
        //假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
        //每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
        //(改：一步一个台阶，两个台阶，三个台阶，.......，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？）
        //注意：给定 n 是一个正整数。
        public int ClimbStairs(int n)
        {//背包里求排列
            //爬到有i个台阶的楼顶，有dp[i]种方法。
            int[] dp = new int[n + 1];
            int[] weight = { 1, 2 };//1,2两种台阶
            dp[0] = 1;
            for(int i = 1;i<= n;i++)
            {
                for (int j = 1; j <= weight.Length; j++)
                {
                    if (i - j >= 0)
                        dp[i] += dp[i - j];
                }
            }
            return dp[n];
        }

        //========================================力扣322 零钱兑换
        //给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
        //计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1
        //你可以认为每种硬币的数量是无限的。
        //1 <= coins.length <= 12
        //1 <= coins[i] <= 231 - 1
        //0 <= amount <= 104
        public int CoinChange(int[] coins, int amount)
        {
            //凑足总额为j所需钱币的最少个数为dp[j]
            int[] dp = new int[amount + 1];
            dp[0] = 0;
            //因为是求最小值，所以dp数组应该初始化为一个最大值
            //否则会在min(dp[j - coins[i]] + 1, dp[j])被初始值覆盖
            for(int i = 1;i<dp.Length;i++)
            {
                dp[i] = int.MaxValue;
            }

            //本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。。
            //所以本题并不强调集合是组合还是排列。
            for (int i = 0;i<coins.Length;i++)
            {// 遍历物品
                for (int j = coins[i];j<= amount;j++)
                {// 遍历背包
                    if (dp[j-coins[i]] != int.MaxValue)//如果dp[j - coins[i]]是初始值则跳过
                        dp[j] = Math.Min(dp[j], dp[j - coins[i]] + 1);//要求的是硬币个数不是硬币金额，所以加1
                }
            }

            if (dp[amount] == int.MaxValue)
                return -1;
            return dp[amount];
        }

        //========================================================力扣279 完全平方数
        //给定正整数n，找到若干过完全平方数（比如1，4，89，16）使他们的和等于n。
        //你需要让组成和的完全平方数的个数最小
        //给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
        public int NumSquares(int n)
        {
            //和为i的完全平方数的最少数量为dp[i]
            int[] dp = new int[n + 1];
            dp[0] = 0;
            for(int i = 1;i<dp.Length;i++)
            {
                dp[i] = int.MaxValue;
            }

            for (int i = 1; i*i <= n; i++)
            {// 遍历物品
                for (int j = 1; j <= n; j++)
                {// 遍历背包
                    if (j-i*i >=0)
                        //dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。
                        dp[j] = Math.Min(dp[j], dp[j - i*i] + 1);
                }
            }
            return dp[n];
        }

        //====================================================力扣139 单词拆分
        //给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
        //拆分时可以重复使用字典中的单词。
        //你可以假设字典中没有重复的单词。
        public bool WordBreak(string s, IList<string> wordDict)
        {
            //字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
            bool[] dp = new bool[s.Length + 1];
            dp[0] = true;
            for(int i = 1;i<=s.Length;i++)
            {// 遍历背包
                for (int j = 0;j<i;j++)
                {// 遍历物品
                    string word = s.Substring(j, i - j);//substr(起始位置，截取的个数)
                    if (wordDict.IndexOf(word) != -1  && dp[j])
                        dp[i] = true;
                }
            }
            return dp[s.Length];
        }



    }
}
